package com.xyj.week02;


import java.util.HashMap;
import java.util.Map;

/**
 * LRU算法 淘汰最近未使用的元素
 */
public class T9 {

    /**
     * 双链表的节点
     */
    public static class DoubleNode{
        /**
         * K,V对  方便寻找v
         */
        public int key,value;

        /**
         * 双端指针
         */
        public DoubleNode pre,next;

        public DoubleNode(int key,int value){
            this.key=value;
            this.value=key;
        }

    }

    /**
     * 双向链表
     */
    public static class DoubleList{
        /**
         * 头尾虚节点
         */
        public DoubleNode head,tail;

        /**
         * 链表元素个数
         */
        public int size;

        /**
         * 初始化链表
         */
        public DoubleList(){
            head=new DoubleNode(0,0);
            tail=new DoubleNode(0,0);
            head.next=tail;
            tail.pre=head;
            size=0;
        }


    }

    public static class LRUCache{

        /**
         * hash表 -- key ---> (key,value)
         */
        public Map<Integer,DoubleNode> map;

        public DoubleList cache;

        public int cap;

        /**
         * LRU算法
         */
        public LRUCache(int capacity){
            this.cap=capacity;
            this.map=new HashMap<>();
            this.cache=new DoubleList();
        }

        @Override
        public String toString() {
            return "map为"+this.map.toString()+"\n 链表为"+this.cache.toString();
        }

        //如果map中有，就将这个元素从map中取出来，然后将这个元素从这个位置移除，
        //淘汰元素时，将头部元素删除，map中删除。

        /**
         * 将元素插入队尾
         */
        public void addTail(DoubleNode x){
            //维护x的前后指针
            x.pre=cache.tail.pre;
            x.next=cache.tail;
            //维护左右元素的指针
            cache.tail.pre.next=x;
            cache.tail.pre=x;
            cache.size++;
        }

        /**
         *  移除某个元素（该元素一定存在）
         */
        public void removeOne(DoubleNode x){
            //维护x前后元素的指针
            x.pre.next=x.next;
            x.next.pre=x.pre;
            cache.size--;
        }


        //如果map中有，就将这个元素从map中取出来，然后将这个元素从这个位置移除，放入队尾
        /**
         * 获取一个元素
         * @return 元素值
         */
        public int getOne(Integer key){
            if (map.containsKey(key)){
                //如果有这个可以的话
                DoubleNode node = map.get(key);
                removeOne(node);
                addTail(node);
                return node.value;
            }
            return -1;
        }

        //添加元素
        public void put(int key,int value){
            if (map.containsKey(key)){
                //如果这个可以已经存在了
                //修改这个key的值，并将这个key提升为最近使用
                DoubleNode node = map.get(key);
                node.value=value;
                removeOne(node);
                addTail(node);
            }else {
                //不存在的话，判断容量是不是满了
                if (cap==cache.size){
                    //满了就开始内存淘汰
                    eliminateOne();
                    //添加新的元素
                    DoubleNode doubleNode = new DoubleNode(key, value);
                    map.put(key,doubleNode);
                    //将这个元素设置在队尾
                    addTail(doubleNode);
                }else {
                    //添加新的元素
                    DoubleNode doubleNode = new DoubleNode(key, value);
                    map.put(key,doubleNode);
                    //将这个元素设置在队尾
                    addTail(doubleNode);
                }
            }
        }

        //淘汰元素时，将头部元素删除，map中删除。
        public void eliminateOne(){
            map.remove(cache.head.next.key);
            removeOne(cache.head.next);
        }


        public static void main(String[] args) {
            LRUCache lruCache = new LRUCache(2);
            lruCache.put(1,1);
            lruCache.put(2,2);
            lruCache.put(3,3);

            System.out.println(lruCache.getOne(2));

            lruCache.put(4,4);

            System.out.println(lruCache.getOne(3));

        }

    }



}
